package twobranchTree.connectright2;

import twobranchTree.connectright.Node;

/**
 * @Date 2020/03/04
 * @author 王光浩
 * @Thinking 使用迭代+层序遍历的方式解决。在第n层将第n+1层的所有节点进行连接
 */
public class MyMethodOne {
	public Node connect(Node root) {
    	Node firstLeft=root; //用于控制层数
    	Node tem=firstLeft;  //用于遍历每一层
    	//进行层序遍历
    	while(firstLeft!=null) {
    		if(tem==null) {  //当tem遍历完该层后进入下一层
    			//找到该层的第一个含有左或右子树的节点
    			while(firstLeft!=null) {
    				if(firstLeft.left!=null || firstLeft.right!=null)
    					break;
    				firstLeft=firstLeft.next;
    			}
    			if(firstLeft!=null)
    				firstLeft=firstLeft.left!=null?firstLeft.left:firstLeft.right;
    			tem=firstLeft;
    		} 
    		else {  //遍历该层的所有节点
    			if(tem.left==null && tem.right==null) //当前节点没有左右子树
    				tem=tem.next;
    			else {
    				if(tem.left!=null && tem.right!=null) //将左右子树连接
    					tem.left.next=tem.right;    
    				Node notnull=(tem.right!=null?tem.right:tem.left);
    				//获取与tem节点在同一层，且在tem节点后面的第一个有子树的节点
    				Node nextNode=tem.next;
    				while(nextNode!=null) {
    					if(nextNode.left!=null || nextNode.right!=null) { 
    						break;
    					}
    					nextNode=nextNode.next;
    				}
    				//将相邻的节点进行连接
    				if(nextNode!=null)
    					notnull.next=nextNode.left!=null?nextNode.left:nextNode.right;
    				//更该tem信息
    				tem=nextNode;
    			}
    		}
    	}
        return root;
    }
}
